//============================================================================
// Name        : DiseñoII.cpp
// Author      : Daniel Rodriguez del Villar, Daniela Velasquez
// Version     :
// Copyright   :
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <string.h>
#include "main.h"

using namespace std;

/* Ciudad mas cercana a la ciudad actual
 * @param:  ciudad actual
 * 		    Solucion actual
 * 		    lista de ciudades no visitadas
 * @return: ciudad mas cercana
 * */
int nearestNeighbor(int i, Solution *s, vector<int> noVisitados) {

	int j;
	float menor = FLT_MAX;
	int posMenor = 0;

	for (j = 0; j < noVisitados.size(); j++) {

		if (i < noVisitados[j]) {
			if (s->C[i][noVisitados[j]] < menor) {
				menor = s->C[i][noVisitados[j]];
				posMenor = noVisitados[j];
			}
		} else if (i != noVisitados[j]) {
			if (s->C[noVisitados[j]][i] < menor) {
				menor = s->C[noVisitados[j]][i];
				posMenor = noVisitados[j];
			}
		}
	}

	return posMenor;
}

/**
 * Encuentra una vecindad para una solucion.
 * @param: una solucion y un grado de variacion.
 * @return: Una lista de intercambios que construyen
 * 			la vecindad.
 */
list<int*> findNeighbors(Solution *sact, int paso) {

	int i, j;
	int* mov;

	list<int*> vecinos;

	for (i = 0; i < sact->cityNumber - paso; i += paso) {
		for (j = i + 1; j < sact->cityNumber; j += paso) {
			mov = (int*) malloc(sizeof(int) * 2);
			mov[0] = i;
			mov[1] = j;
			vecinos.push_back(mov);
		}
	}
	return vecinos;
}

/* Elimina la ciudad recien visitada
 * de la lista de ciudades no visitadas
 * @param:  ciudad actual
 * 		    lista de ciudades no visitadas
 * @return: ciudades no visitadas
 * */
vector<int> deleteCity(int i, vector<int> noVisitados) {

	vector<int>::iterator it = noVisitados.begin();

	while (*it != i && it != noVisitados.end())
		it++;

	if (*it == i)
		noVisitados.erase(it);

	return noVisitados;
}

Solution *initialSolution(vector<Node> listaNodos) {
	Solution *is = new Solution(listaNodos.size(), listaNodos);
	return is;
}

Solution *randomSolution(vector<Node> listaNodos) {
	Solution *is = new Solution(listaNodos.size(), listaNodos);
	return Operator::perturbation(is);
}

/**
 * Dada una lista de ciudades, se construye una solucion inicial
 * uniendo las ciudades con su vecino mas cercano
 * @param: Un vector de ciudades.
 * @return: Una solucion.
 */

Solution *ISNeighbort(vector<Node> listaNodos) {

	Solution *is = new Solution(listaNodos.size(), listaNodos);

	int i = 0;
	int masCercano;

	vector<int> noVisitados;

	noVisitados.clear();

	//Lleno a noVisitados con las ciudades no visitadas.
	for (int j = 0; j < is->cityNumber; j++) {
		noVisitados.push_back(j);
	}

	i = rand() % (is->cityNumber - 1);

	//Coloco la primera ciudad
	is->tour[0] = i + 1;
	is->pos[i] = 0;
	is->cost = 0;

	noVisitados = deleteCity(i, noVisitados);

	for (int j = 1; j < is->cityNumber; j++) {

		masCercano = nearestNeighbor(i, is, noVisitados);

		is->tour[j] = masCercano + 1;
		is->pos[masCercano] = j;

		if (i < masCercano)
			is->cost += is->C[i][masCercano];
		else
			is->cost += is->C[masCercano][i];

		i = masCercano;

		noVisitados = deleteCity(i, noVisitados);
	}
	is->cost += is->getCost(0, is->cityNumber - 1);
	return is;
}

int main(int argc, char* argv[]) {

	srand(time(NULL));

	if (argc < 3) {

		cout << "Falta nombre de archivo .tsp." << endl;
		cout << "Falta el flag de invocacion." << endl;

		cout << endl;
		cout << "	./main 'archivo.tsp' 'algoritmo'" << endl;
		cout << endl;

		cout << "Con algoritmo: " << endl;
		cout << "	1 ----------- Busqueda Local" << endl;
		cout << "	2 ----------- Busqueda Local Iterada" << endl;
		cout << "	3 ----------- Busqueda Tabu" << endl;
		cout << "	4 ----------- Recocido Simulado" << endl;
		cout << "	5 ----------- GRASP" << endl;
		cout << "	6 ----------- AS" << endl;
		cout << endl;

		return -1;
	}

	// Lista de Nodos.
	vector<Node> nodelst;

	// Lee el archivo.
	Parser psr = Parser();
	nodelst = psr.leerArchivo(argv[1]);

	// Crea las soluciones.
	Solution *sOpt = NULL;
	Solution *is = initialSolution(nodelst);

	if (atoi(argv[2]) == 1) { // Busqueda Local.

		if (argc < 5)
			cout << "Parametros: Maximo de iteraciones, Maximo de NoMejoras\n";
		else {
			cout << "Corriendo Busqueda Local" << endl;

			is = new Solution(nodelst.size(), nodelst);
			is = GRASP::Greedy(is, 0);
			sOpt = LS::LocalSearchBI(is, atoi(argv[3]), atoi(argv[4]));
		}

	} else if (atoi(argv[2]) == 2) { // Busqueda Local Iterada.

		if (argc < 5)
			cout << "Parametros: Maximo de iteraciones, Maximo de NoMejoras\n";
		else {
			cout << "Corriendo ILS" << endl;

			is = GRASP::Greedy(is, 0);
			sOpt = ILS::Ils(is, atoi(argv[3]), atoi(argv[4]));
		}

	} else if (atoi(argv[2]) == 3) { // Busqueda Tabu.

		if (argc < 6) {
			printf("Parametros:\n");
			printf("	Maximo de iteraciones\n");
			printf("	No mejoras\n");
			printf("	Tam. Lista Tabu\n");

		} else {
			cout << "Corriendo Busqueda Tabu" << endl;

			int numIter = atoi(argv[3]);
			int maxNo = atoi(argv[4]);
			int LTsize = atoi(argv[5]);

			is = ISNeighbort(nodelst);
			sOpt = TABU::TABUSearch(is, numIter, maxNo, LTsize);
		}
	} else if (atoi(argv[2]) == 4) { // Recocido Simulado.

		if (argc < 9) {
			printf("Parametros:\n");
			printf("	Maximo de iteraciones\n");
			printf("	alpha\n");
			printf("	betha\n");
			printf("	Temperatura\n");
			printf("	Intensidad de cambio de temperatura (K)\n");
			printf("	Numero maximo de mejoras en un nivel (A)\n");
		} else {
			cout << "Corriendo Recocido Simulado" << endl;

			is = new Solution(nodelst.size(), nodelst);
			is = GRASP::Greedy(is, 0);

			double alpha = atof(argv[4]);
			double betha = atof(argv[5]);

			//100, 0.5, 1.02, 70
			sOpt = SA::SimulatedAnnealing(is, atoi(argv[3]), alpha, betha,
					atoi(argv[6]), atoi(argv[7]), atoi(argv[8]));
		}
	} else if (atoi(argv[2]) == 5) { // GRASP.

		if (argc < 7) {
			printf("Parametros:\n");
			printf("	Maximo de iteraciones\n");
			printf("	alpha\n");
			printf("	No mejoras de busqueda local.\n");
			printf("	Metodo Greedy:\n");
			printf("		1 ------ SampleGreedy.\n");
			printf("		2 ------ Greedy.\n");
			printf("		3 ------ GreedyRandomizedConstruction.\n");
		} else {
			cout << "Corriendo GRASP." << endl;

			is = new Solution(nodelst.size(), nodelst);
			sOpt = GRASP::Grasp(is, atoi(argv[3]), atoi(argv[4]),
					atoi(argv[5]), atoi(argv[6]));
		}
	} else if (atoi(argv[2]) == 6) { //Colonia de hormigas.

		if (argc < 7) {
			printf("Parametros:\n");
			printf("	Maximo de iteraciones\n");
			printf("	Num Hormigas\n");
			printf("	Feromona Maxima\n");
			printf("	Feromona Minima\n");
			printf("	alpha\n");
			printf("	betha\n");

		} else {
			cout << "Corriendo Colonia de Hormigas" << endl;

			double alpha = atof(argv[7]);//0.5;//Regulador de Feromona
			double betha = atof(argv[8]); //3;//Regulador de visibilidad

			sOpt = AC::AntColonyMinMax(nodelst, atoi(argv[3]), atoi(argv[4]), atof(
					argv[5]), atof(argv[6]), alpha, betha);
		}
	} else if (atoi(argv[2]) == 7) { //Algoritmo Genetico.

		if (argc < 10) {
			printf("Parametros:\n");
			printf("	Tamaño de la poblacion\n");
			printf("	Numero de Generaciones\n");
			printf("	Tamaño del torneo\n");
			printf("	Numero maximo de hijos a crear por generacion\n");
			printf("	Probabilidad de cruce\n");
			printf("	Probabilidad de matacion\n");
			printf("	porcentaje de soluciones greedys de la poblacion\n");

		} else {
			cout << "Corriendo Algoritmo Genetico" << endl;

			Solution *problem = new Solution(nodelst.size(), nodelst);
			sOpt = GA::geneticAlgorithm(problem, atoi(argv[3]), atoi(argv[4]),
					atoi(argv[5]), atoi(argv[6]), atof(argv[7]), atof(argv[8]),
					atof(argv[9]));
		}
	} else {
		cout << "Debe seleccionar un algoritmo valido\n";
	}

	if (sOpt != NULL) {
		//char *fileName = strcat(argv[1], ".sol");
		sOpt->printWithFormat();
		//sOpt->print();
		//cout << "Costo: " << sOpt->recomputeCost();
	}

	delete is;
	return 0;
}
